<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Minimum Spanning Tree Graph Algorithm</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="minimum-spanning-tree-graph-algorithm">Minimum Spanning Tree Graph Algorithm</h1>
<p>给定一个全连接的无向图， 生成最小树</p>
<ul>
<li>这棵树连接了所有顶点</li>
<li>这棵树的所有边的和是最小的</li>
</ul>
<h1 id="1-kruskals-algorithm">1. Kruskal's algorithm</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=fAuF0EuZVCk&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=3">https://www.youtube.com/watch?v=fAuF0EuZVCk&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=3</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/KruskalMST.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/KruskalMST.java</a></li>
</ul>
<p>时间复杂度 O(ElgE + E)</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\mini1.png" alt="mini1.png"></p>
<p>思路其实就是并查集， 先对edge排序。 然后逐个遍历edge.</p>
<ul>
<li>如果edge的两个端点在不同的set, 则合并两个set, 并且将此edge加入result list</li>
<li>如果edge的两个端点已经在同一个set， 则跳过</li>
</ul>
<p>当所有端点都在同一个set后，返回result list</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\mini1b.png" alt="mini1b.png"></p>
<pre><code class="language-java"><div><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">KruskalMST</span> </span>{
    <span class="hljs-comment">/**
     * Comparator to sort edges by weight in non decreasing order
     */</span>
    <span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">EdgeComparator</span> <span class="hljs-keyword">implements</span> <span class="hljs-title">Comparator</span>&lt;<span class="hljs-title">Edge</span>&lt;<span class="hljs-title">Integer</span>&gt;&gt; </span>{
        <span class="hljs-meta">@Override</span>
        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">compare</span><span class="hljs-params">(Edge&lt;Integer&gt; edge1, Edge&lt;Integer&gt; edge2)</span> </span>{
            <span class="hljs-keyword">if</span> (edge1.getWeight() &lt;= edge2.getWeight()) {
                <span class="hljs-keyword">return</span> -<span class="hljs-number">1</span>;
            } <span class="hljs-keyword">else</span> {
                <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
            }
        }
    }

    <span class="hljs-keyword">public</span> List&lt;Edge&lt;Integer&gt;&gt; getMST(Graph&lt;Integer&gt; graph) {
        List&lt;Edge&lt;Integer&gt;&gt; allEdges = graph.getAllEdges();
        EdgeComparator edgeComparator = <span class="hljs-keyword">new</span> EdgeComparator();

        <span class="hljs-comment">//sort all edges in non decreasing order</span>
        Collections.sort(allEdges, edgeComparator);
        DisjointSet disjointSet = <span class="hljs-keyword">new</span> DisjointSet();

        <span class="hljs-comment">//create as many disjoint sets as the total vertices</span>
        <span class="hljs-keyword">for</span> (Vertex&lt;Integer&gt; vertex : graph.getAllVertex()) {
            disjointSet.makeSet(vertex.getId());
        }

        List&lt;Edge&lt;Integer&gt;&gt; resultEdge = <span class="hljs-keyword">new</span> ArrayList&lt;Edge&lt;Integer&gt;&gt;();

        <span class="hljs-keyword">for</span> (Edge&lt;Integer&gt; edge : allEdges) {
            <span class="hljs-comment">//get the sets of two vertices of the edge</span>
            <span class="hljs-keyword">long</span> root1 = disjointSet.findSet(edge.getVertex1().getId());
            <span class="hljs-keyword">long</span> root2 = disjointSet.findSet(edge.getVertex2().getId());

            <span class="hljs-comment">//check if the vertices are in same set or different set</span>
            <span class="hljs-comment">//if verties are in same set then ignore the edge</span>
            <span class="hljs-keyword">if</span> (root1 == root2) {
                <span class="hljs-keyword">continue</span>;
            } <span class="hljs-keyword">else</span> {
                <span class="hljs-comment">//if vertices are in different set then add the edge to result and union these two sets into one</span>
                resultEdge.add(edge);
                disjointSet.union(edge.getVertex1().getId(), edge.getVertex2().getId());
            }

        }
        <span class="hljs-keyword">return</span> resultEdge;
    }

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span> </span>{
        Graph&lt;Integer&gt; graph = <span class="hljs-keyword">new</span> Graph&lt;Integer&gt;(<span class="hljs-keyword">false</span>);
        graph.addEdge(<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">4</span>);
        graph.addEdge(<span class="hljs-number">1</span>, <span class="hljs-number">3</span>, <span class="hljs-number">1</span>);
        graph.addEdge(<span class="hljs-number">2</span>, <span class="hljs-number">5</span>, <span class="hljs-number">1</span>);
        graph.addEdge(<span class="hljs-number">2</span>, <span class="hljs-number">6</span>, <span class="hljs-number">3</span>);
        graph.addEdge(<span class="hljs-number">2</span>, <span class="hljs-number">4</span>, <span class="hljs-number">2</span>);
        graph.addEdge(<span class="hljs-number">6</span>, <span class="hljs-number">5</span>, <span class="hljs-number">2</span>);
        graph.addEdge(<span class="hljs-number">6</span>, <span class="hljs-number">4</span>, <span class="hljs-number">3</span>);
        graph.addEdge(<span class="hljs-number">4</span>, <span class="hljs-number">7</span>, <span class="hljs-number">2</span>);
        graph.addEdge(<span class="hljs-number">3</span>, <span class="hljs-number">4</span>, <span class="hljs-number">5</span>);
        graph.addEdge(<span class="hljs-number">3</span>, <span class="hljs-number">7</span>, <span class="hljs-number">8</span>);
        KruskalMST mst = <span class="hljs-keyword">new</span> KruskalMST();
        List&lt;Edge&lt;Integer&gt;&gt; result = mst.getMST(graph);
        <span class="hljs-keyword">for</span> (Edge&lt;Integer&gt; edge : result) {
            System.out.println(edge.getVertex1() + <span class="hljs-string">" "</span> + edge.getVertex2());
        }
    }
}
</div></code></pre>
<h1 id="2-prime-algirthm">2. Prime algirthm</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=oP2-8ysT3QQ&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=4">https://www.youtube.com/watch?v=oP2-8ysT3QQ&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=4</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/PrimMST.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/PrimMST.java</a></li>
<li><a href="https://en.wikipedia.org/wiki/Prim%27s_algorithm">https://en.wikipedia.org/wiki/Prim's_algorithm</a></li>
</ul>
<p>和Dijkstra的算法很像，就是有一点不同，小顶堆入堆时候的distance，不是到起始点的总距离，而就是该edge本身的长度，不累加。</p>
<p>tushare roy和wiki说时间复杂度 O(ElgV)   E 是边数， V是顶点数目，  这和他们使用小顶堆的思路有关系。 他们算法的小顶堆大小固定的，就是顶点数目V</p>
<p>而我们代码里面的小顶堆，是从无到有，逐步添加进去的。</p>
<p>回过头来看，其实Kruskal和Prime算法的本质是一样的，就是不断的挑选&quot;当前未遍历的最小边&quot; 来merge 节点。</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\mini1c.png" alt="mini1c.png"></p>
<p>起始点A, 最小堆s, 答案列表result</p>
<ol>
<li>
<p>遍历A点, 将A的相邻边加入小顶堆</p>
<pre><code> heappush(s, (1, D, AD))
 heappush(s, (3, B, AB))
</code></pre>
</li>
<li>
<p>遍历D点, 将D的相邻边加入小顶堆</p>
<pre><code> s的顶点是D, result.append(AD)
 heappush(s, (1, C, CD))
 heappush(s, (3, B, BD))
 heappush(s, (6, E, DE))
</code></pre>
</li>
<li>
<p>遍历C点, 将C的相邻边加入小顶堆</p>
<pre><code> s的顶点是C, result.append(CD)
 heappush(s, (1, B, BC))
 heappush(s, (4, F, CF))
 heappush(s, (5, E, CE))
</code></pre>
</li>
<li>
<p>编译B点, 将B的相邻边加入小顶堆</p>
<pre><code> s的顶点是B, result.append(BC)
</code></pre>
</li>
<li>
<p>遍历F点, 将F的相邻边加入小顶堆</p>
<pre><code> s的顶点是F, result.append(CF)
 heappush(s, (2, E, EF))
</code></pre>
</li>
<li>
<p>遍历最后的E点</p>
<pre><code> s的顶点是E, result.append(EF)
</code></pre>
</li>
</ol>
<p>最终result = [AD, CD, BC, CF, EF]</p>

    </body>
    </html>